# 快速排序
# test= [48, 12, 64, 82, 25, 36, 55, 79, 91, 4]
# def partition(arr, low, high):
#     pivot = arr[low]
#     while low < high:
#         while low < high and arr[high] > pivot:
#             high -= 1
#         arr[low] = arr[high]
#         while low < high and arr[low] < pivot:
#             low += 1
#         arr[high] = arr[low]
#     arr[low] = pivot
#     return low
# def quickSort(arr, low, high):
#     if low < high:
#         p = partition(arr, low, high)
#         quickSort(arr, low, p-1)
#         quickSort(arr, p+1, high)
# quickSort(test, 0, len(test) - 1)
# print(test)



# def quick_sort(arr):
#     if len(arr) <= 1:
#         return arr
#
#     # 选择基准元素（这里选择最后一个元素）
#     pivot = arr[-1]
#     # 分区：小于基准的元素放在左侧，大于基准的元素放在右侧
#     left = [x for x in arr[:-1] if x <= pivot]
#     right = [x for x in arr[:-1] if x > pivot]
#     # 递归排序并合并
#     return quick_sort(left) + [pivot] + quick_sort(right)
#
# # 示例
# arr = [3, 6, 8, 10, 1, 2, 1]
# sorted_arr = quick_sort(arr)
# print(sorted_arr)  # 输出: [1, 1, 2, 3, 6, 8, 10]
